package com.tgy.leetcode;

import lombok.Data;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: tgy
 * @Date: 12/9/20 11:47 AM
 *
 * https://leetcode-cn.com/problems/edit-distance/
 */

enum OperationType{

    REPLACE,DELETE,ADD
}

@Data
class Operation{

    /**
     * 1 替换
     *  y 位置替换成x位置
     * 2 删除
     *  删除x位置元素
     * 3 添加
     *  在x位置后面添加y元素
     */
    private OperationType type;

    private int x;

    private int y;

    public Operation(OperationType type, int x, int y) {
        this.type = type;
        this.x = x;
        this.y = y;
    }

    public Operation(OperationType type, int x) {

        this(type,x,-1);
    }

}


public class _72_编辑距离_01 {

    public List<Operation> minDistance(String word1, String word2) {

        if (word1 == null || word2 == null) {

            return null;
        }

        char[] w1 = word1.toCharArray();
        char[] w2 = word2.toCharArray();

        int[][] dp = new int[w1.length + 1][w2.length +1];

        for (int i = 1; i <= w1.length ; i++) {

            dp[i][0] = i;
        }

        for (int i = 1; i <= w2.length; i++) {

            dp[0][i] = i;
        }

        for (int i = 1; i <= w1.length ; i++) {

            for (int j = 1; j <= w2.length; j++) {

                int leftTop = dp[i - 1][j-1];

                if (w1[i - 1] != w2[j - 1]) {

                    leftTop++;
                }

                dp[i][j] = Math.min(leftTop,Math.min(dp[i][j-1] + 1,dp[i-1][j] + 1));
            }
        }

        for (int i = 0; i <= w1.length; i++) {

            System.out.println(Arrays.toString(dp[i]));
        }

        int x = w1.length;
        int y = w2.length;

        List<Operation> operations = new ArrayList<>();

        while (true) {

            if (x== 0 && y == 0) {

                break;
            }

            if (x > 0 && y > 0) {
                int leftTop = dp[x-1][y-1];
                int left = dp[x][y-1] + 1;
                int top = dp[x-1][y] + 1;

                boolean flag = false;
                if (w1[x - 1] != w2[y - 1]) {

                    leftTop++;

                    flag = true;
                }

                int cur = dp[x][y];

                if (cur == left) {



                    System.out.println("在" + w1[x - 1] + "右边增加" + w2[y - 1]);
                    operations.add(new Operation(OperationType.ADD,x-1,y-1));

                    y--;
                }else if (cur == top) {

                    System.out.println("删除" + w1[x - 1]);
                    operations.add(new Operation(OperationType.DELETE,x-1));
                    x--;
                }else {

                    if (flag) {
                        System.out.println("使用" + w1[x - 1] + "替换" + w2[y - 1]);

                        operations.add(new Operation(OperationType.REPLACE,x-1,y-1));
                    }
                    x--;
                    y--;
                }
            }else if (x == 0) {

                System.out.println("右边增加" + w2[y - 1]);
                operations.add(new Operation(OperationType.ADD,-1,y-1));
                y--;
            }else if (y == 0) {

                System.out.println("删除" + w1[x - 1]);
                operations.add(new Operation(OperationType.DELETE,x-1));
                x--;
            }
        }

        return operations;
    }

    public int minDistance01(String word1, String word2) {

        if (word1 == null || word2 == null) {

            return 0;
        }

        char[] w1 = word1.toCharArray();
        char[] w2 = word2.toCharArray();

        if (w1.length * w2.length == 0) {

            return w1.length + w1.length;
        }

        if (w1.length > w2.length) {

            char[] tmp = w1;
            w1 = w2;
            w2 = tmp;
        }

        int[] dp = new int[w1.length + 1];

        for (int i = 0; i < dp.length; i++) {

            dp[i] = i;
        }

        int cur = 0,pre;
        for (int i = 1; i <= w2.length; i++) {

            cur = dp[0];
            dp[0] = i;
            for (int j = 1; j <= w1.length; j++) {

                /**
                 * pre 左上
                 *   w2[i - 1] != w1[j - 1] --> 替换 i = j
                 * dp[j - 1] 左
                 *  增加 w1[j - 1]
                 *
                 * dp[j] 上
                 *  删除 w2[i - 1]
                 *
                 */
                pre = cur;
                cur = dp[j];

                boolean flag = false;
                // "a" "ab"
                if (w2[i - 1] != w1[j - 1]) {
                    pre++;
                    flag = true;
                }

                int leftTop = pre;
                int left = dp[j-1];
                int top = dp[j];

                int min = Math.min(dp[j - 1] + 1,Math.min(dp[j] + 1 ,pre));

                if (min == left) {

                    System.out.println("插入" + w1[j - 1]);
                }else if (min == top) {

                    System.out.println("删除" + w2[i - 1]);
                }else {

                    if (flag) {

                        System.out.println("使用" + w1[j - 1] + "替换" + w2[i - 1]);
                    }else {

                        System.out.println(w1[j - 1] + "与" + w2[i - 1] + "相等，什么都做");
                    }
                }

                dp[j] = min;
            }

//            System.out.println(Arrays.toString(dp));
        }


        return dp[w1.length];
    }
}
